package heap

func buildMaxHeap(a []int, n int) {
	// 数组序列堆化
	for i := n / 2; i >= 1; i-- {
		heapifyUpToDown(a, i, n)
	}
}

// 按照ASCII排序，索引从1开始，一共n个元素
func HeapSort(a []int, n int) {
	// 建立一个大顶堆
	buildMaxHeap(a, n-1)

	k := n - 1
	for k >= 1 {
		swap(a, 1, k)
		heapifyUpToDown(a, 1, k-1)
		k--
	}
}

//从上往下堆化
func heapifyUpToDown(a []int, top, count int) {
	for i := top; i <= count/2; {
		maxIndex := i
		if a[i] < a[i*2] {
			maxIndex = i * 2
		}

		if i*2+1 <= count && a[maxIndex] < a[i*2+1] {
			maxIndex = i*2 + 1
		}

		// 找到了最大的节点
		if maxIndex == i {
			break
		}

		swap(a, i, maxIndex)
		i = maxIndex
	}
}

func swap(a []int, i int, j int) {
	tmp := a[i]
	a[i] = a[j]
	a[j] = tmp
}
